// BEGIN CUT HERE
/*
PROBLEM STATEMENT
There is a community of art lovers who meet from time to time and trade images with each other.  Each image 
transaction must obey the following rules:

The price at which the image is sold must be greater than or equal to the price at which it was bought.
No trader is allowed to buy the same image more than once.


A new image has just appeared on the market.  Trader 0 bought it from an unknown artist for the price of '0', and he 
is now ready to trade it among his fellow art lovers.  You are given a vector <string> price, where the j-th character 
of the i-th element is a digit representing the price at which trader j will buy the image from trader i.  '0' is the 
lowest price, and '9' is the highest.  Assuming all transactions obey the rules mentioned above, determine the longest 
possible sequence of transactions involving the new image.  After all the transactions are done, return the number of 
people who have owned the image at some point in time, including both the final owner and trader 0.


DEFINITION
Class:ImageTraders
Method:maxOwners
Parameters:vector <string>
Returns:int
Method signature:int maxOwners(vector <string> price)


CONSTRAINTS
-price will contain exactly N elements, where N is between 2 and 15, inclusive.
-Each element of price will contain exactly N characters.
-Each element of price will contain only digits ('0'-'9').


EXAMPLES

0)
{
"01",
"10"
}

Returns: 2

Trader 0 can sell the image to trader 1 for the price of '1'.  Both traders were owners of the image, so the answer is 
2.

1)
{
"022",
"101",
"110"
}


Returns: 2

We have 3 traders here. Trader 0 can sell the image to either trader 1 or trader 2 for the price of '2'.  In both 
cases, the buyer would have to sell the image for a price of at least '2', which is impossible.  Therefore, the 
maximal number of owners is 2.

2)
{
"01231",
"00231",
"00031",
"00002",
"00000"
}

Returns: 4

Here the image can have 4 owners:

Trader 0 sells the image to trader 1 for the price of '1'.
Trader 1 sells the image to trader 2 for the price of '2'.
Trader 2 sells the image to trader 3 for the price of '3'.


3)
{
"15555",
"11111",
"15111",
"11111",
"11111"
}

Returns: 3

Trader 0 can sell the image to trader 2 for the price of '5'.  Then, trader 2 can sell it to trader 1.

4)
{
"0100000000",
"0020000000",
"0003000000",
"0000400000",
"0000050000",
"0000006000",
"0000000700",
"0000000080",
"0000000009",
"1111111111"
}

Returns: 10

The image can be traded among all the traders in the following sequence: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

*/
// END CUT HERE
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <bitset>
using namespace std;

	int m[16][10][1<<15]; // who, price, free
class ImageTraders {
public:
	int p[16][16];
	int N;


	int solve(int who, int price, unsigned frees)
	{
		if(who<0 || who>=N
			|| price<0 || price>9
			|| frees>=(1<<N))
			return 0;

		int md=m[who][price][frees];
		if(md!=0)
			return -1;

		int res=0; // it self

		bitset<16> b(frees);
		for(int to=0;to<N;to++)
		{
			if(b.test(to) &&
				p[who][to]>=price)
			{
				b[to]=false;
				res=max(res,
					solve(to, p[who][to],b.to_ulong()));
				b[to]=true;
			}
		}
		++ res;
		m[who][price][frees]=res;
		return res;
	}


    int maxOwners(vector <string> price) {
		N=price.size();
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				p[i][j]=price[i][j]-'0';

		memset(m, 0, 16*10*(1<<15));

		bitset<16> bfree;
		for(int i=0;i<N;i++)
			bfree[i]=true;

		bfree[0]=false;

		return solve(0,0,(unsigned)bfree.to_ulong());
    }

};

// BEGIN CUT HERE
#define ARRSIZE(x) (sizeof(x)/sizeof(x[0]))

template<typename T> void print( T a ) {
    cerr << a;
}
static void print( long long a ) {
    cerr << a << "L";
}
static void print( string a ) {
    cerr << '"' << a << '"';
}
template<typename T> void print( vector<T> a ) {
    cerr << "{";
    for ( int i = 0 ; i != a.size() ; i++ ) {
        if ( i != 0 ) cerr << ", ";
        print( a[i] );
    }
    cerr << "}" << endl;
}
template<typename T> void eq( int n, T have, T need ) {
    if ( have == need ) {
        cerr << "Case " << n << " passed." << endl;
    } else {
        cerr << "Case " << n << " failed: expected ";
        print( need );
        cerr << " received ";
        print( have );
        cerr << "." << endl;
    }
}
template<typename T> void eq( int n, vector<T> have, vector<T> need ) {
    if( have.size() != need.size() ) {
        cerr << "Case " << n << " failed: returned " << have.size() << " elements; expected " << need.size() << " elements.";
        print( have );
        print( need );
        return;
    }
    for( int i= 0; i < have.size(); i++ ) {
        if( have[i] != need[i] ) {
            cerr << "Case " << n << " failed. Expected and returned array differ in position " << i << ".";
            print( have );
            print( need );
            return;
        }
    }
    cerr << "Case " << n << " passed." << endl;
}
static void eq( int n, string have, string need ) {
    if ( have == need ) {
        cerr << "Case " << n << " passed." << endl;
    } else {
        cerr << "Case " << n << " failed: expected ";
        print( need );
        cerr << " received ";
        print( have );
        cerr << "." << endl;
    }
}
// END CUT HERE


// BEGIN CUT HERE
void main( int argc, char* argv[] ) {
    {
        string priceARRAY[] = {
           "01",
           "10"
           };
        vector <string> price( priceARRAY, priceARRAY+ARRSIZE(priceARRAY) );
        ImageTraders theObject;
        eq(0, theObject.maxOwners(price),2);
    }
    {
        string priceARRAY[] = {
           "022",
           "101",
           "110"
           }
           ;
        vector <string> price( priceARRAY, priceARRAY+ARRSIZE(priceARRAY) );
        ImageTraders theObject;
        eq(1, theObject.maxOwners(price),2);
    }
    {
        string priceARRAY[] = {
           "01231",
           "00231",
           "00031",
           "00002",
           "00000"
           };
        vector <string> price( priceARRAY, priceARRAY+ARRSIZE(priceARRAY) );
        ImageTraders theObject;
        eq(2, theObject.maxOwners(price),4);
    }
    {
        string priceARRAY[] = {
           "15555",
           "11111",
           "15111",
           "11111",
           "11111"
           };
        vector <string> price( priceARRAY, priceARRAY+ARRSIZE(priceARRAY) );
        ImageTraders theObject;
        eq(3, theObject.maxOwners(price),3);
    }
    {
        string priceARRAY[] = {
           "0100000000",
           "0020000000",
           "0003000000",
           "0000400000",
           "0000050000",
           "0000006000",
           "0000000700",
           "0000000080",
           "0000000009",
           "1111111111"
           };
        vector <string> price( priceARRAY, priceARRAY+ARRSIZE(priceARRAY) );
        ImageTraders theObject;
        eq(4, theObject.maxOwners(price),10);
    }
}
// END CUT HERE

